/********************************************************/
/*	Copyright (C) 2016 Gong Li Bin		 	*/
/*	Project:	GlbLib-1.0.0			*/
/*	Author:		gong_libin			*/
/*	Date:		2016_06_01			*/
/*	File:		GlbAcbm.cpp			*/
/********************************************************/

#include "GlbAcbm.h"

namespace GlbCls
{

CGlbAcbm::CGlbAcbm()
{
	m_pstTree = NULL;
}

CGlbAcbm::~CGlbAcbm()
{
	if (NULL != m_pstTree) {
		GlbFree((void**)&m_pstTree);
	}
}

void CGlbAcbm::GlbAcbmShift()
{
	GlbAcbmBCShift();
	GlbAcbmGSShiftInit();
	GlbAcbmGSShift();

	return;
}

void CGlbAcbm::GlbAcbmClean()
{
	if (NULL != m_pstTree) {
		if (NULL != m_pstTree->m_pstRoot) {
			GlbAcbmTreeClean(m_pstTree->m_pstRoot);
			GlbFree((void**)&m_pstTree->m_pstRoot);
		}
		GlbFree((void**)&m_pstTree);
	}

	return;
}

void CGlbAcbm::GlbAcbmGSShift()
{
	int iOne = 0;
	int iTwo = 0;
	int iOneLen = 0;
	int iTwoLen = 0;
	UCHAR* puszOne = NULL;
	UCHAR* puszTwo = NULL;

	for (iOne = 0; iOne < m_pstTree->m_iPtnCount; iOne ++) {
		for (iTwo = 0; iTwo < m_pstTree->m_iPtnCount; iTwo ++) {
			puszOne = (m_pstTree->m_pstPtnList + iOne)->m_uszData;
			iOneLen = (m_pstTree->m_pstPtnList + iOne)->m_iLength;
			puszTwo = (m_pstTree->m_pstPtnList + iTwo)->m_uszData;
			iTwoLen = (m_pstTree->m_pstPtnList + iTwo)->m_iLength;
			GlbAcbmSetGSShift2(puszOne, iOneLen, puszTwo, iTwoLen);
		}
	}

	return;
}

void CGlbAcbm::GlbAcbmBCShift()
{
	int iOne = 0;
	int iTwo = 0;
	UCHAR ucVal = '\0';

	for (iOne = 0; iOne < GLB_ACBM; iOne ++) {
		m_pstTree->m_iBCShift[iOne] = m_pstTree->m_iMinPtnSize;
	}


	for (iOne = m_pstTree->m_iMinPtnSize - 1; iOne > 0; iOne --) {
		for (iTwo = 0; iTwo < m_pstTree->m_iPtnCount; iTwo ++) {
			ucVal = (m_pstTree->m_pstPtnList + iTwo)->m_uszData[iOne];
			ucVal = tolower(ucVal);
			m_pstTree->m_iBCShift[ucVal] = iOne;
			if ((ucVal > 'a') && (ucVal < 'z')) {
				m_pstTree->m_iBCShift[ucVal - 32] = iOne;
			}
		}
	}

	return;
}

void CGlbAcbm::GlbAcbmGSShiftInit()
{
	GlbAcbmGSShiftInitCore(m_pstTree->m_pstRoot, m_pstTree->m_iMinPtnSize);

	return;
}

void CGlbAcbm::GlbAcbmTreeClean(GLBACBMNODE_S* pstRoot)
{
	int iCount = 0;

	for (iCount = 0; iCount < GLB_ACBM; iCount ++) {
		if ((iCount >= 'A') && (iCount <= 'Z')) continue;
		if (NULL != pstRoot->m_pstChild[iCount]) {
			GlbAcbmTreeClean(pstRoot->m_pstChild[iCount]);
			GlbFree((void**)&pstRoot->m_pstChild[iCount]);
		}
	}

	return;
}

int CGlbAcbm::GlbAcbmGSShiftInitCore(GLBACBMNODE_S* pstRoot, int iShift)
{
	int iCount = 0;

	if (-2 != pstRoot->m_iLabel) {
		pstRoot->m_iGSShift = iShift;
	}

	for (iCount = 0; iCount < GLB_ACBM; iCount ++) {
		if ((iCount >= 'A') && (iCount <= 'Z')) continue;
		if (NULL != pstRoot->m_pstChild[iCount]) {
			GlbAcbmGSShiftInitCore(pstRoot->m_pstChild[iCount], iShift);
		}
	}

	return GLB_SUCCESS;
}

int CGlbAcbm::GlbAcbmTreeBuild(GLBACBMDATA_S* pstData, int iNumber)
{
	int iVal = 0;
	int iMin = 0;
	int iMax = 0;
	int iSize = 0;
	int iCount = 0;
	int iPtnLen = 0;
	UCHAR ucValue = '\0';
	GLBACBMNODE_S* pstNode = NULL;
	GLBACBMNODE_S* pstRoot = NULL;
	GLBACBMNODE_S* pstParent = NULL;

	iMin = iSize = sizeof(pstData->m_uszData);
	if (NULL != (pstRoot = (GLBACBMNODE_S*)GlbMalloc(sizeof(GLBACBMNODE_S)))) {
		pstRoot->m_iDepth = 0;
		pstRoot->m_iLabel = -2;

		for (iCount = 0 ; iCount < iNumber; iCount ++) {
			if ((iPtnLen = (pstData + iCount)->m_iLength) > 0) {
				if (iPtnLen > iSize) {
					iPtnLen = iSize;
				}
				if (iPtnLen > iMax) {
					iMax = iPtnLen;
				}
				if (iPtnLen < iMin) {
					iMin = iPtnLen;
				}

				pstParent = pstRoot;
				for (iVal = 0; iVal < iPtnLen; iVal ++) {
					ucValue = ((pstData + iCount)->m_uszData)[iVal];
					ucValue = tolower(ucValue);
					if (NULL == pstParent->m_pstChild[ucValue]) {
						break;
					}
					pstParent = pstParent->m_pstChild[ucValue];
				}

				if (iVal < iPtnLen) {
					for (; iVal < iPtnLen; iVal ++) {
						ucValue = ((pstData + iCount)->m_uszData)[iVal];
						ucValue = tolower(ucValue);
						if (NULL != (pstNode = (GLBACBMNODE_S*)GlbMalloc(sizeof(GLBACBMNODE_S)))) {
							pstNode->m_iLabel = -1;
							pstNode->m_ucVal = ucValue;
							pstNode->m_iDepth = iVal + 1;
	
							pstParent->m_pstChild[ucValue] = pstNode;
							if ((ucValue >= 'a') && (ucValue <= 'z')) {
								pstParent->m_pstChild[ucValue - 32] = pstNode;
							}
							pstParent->m_ucChild = ucValue;
							pstParent->m_iChild ++;

							pstNode->m_pstParent = pstParent;
							pstParent = pstNode;
						}
						else {
							goto GlbError;
						}
					}
				}
			}
			else {
				continue;
			}
			pstParent->m_iLabel = iCount;
		}

		m_pstTree->m_pstPtnList = pstData;
		m_pstTree->m_iPtnCount = iNumber;
		m_pstTree->m_iMinPtnSize = iMin;
		m_pstTree->m_pstRoot = pstRoot;
		m_pstTree->m_iMaxDepth = iMax;
	}
	else {
		goto GlbError;
	}

	return GLB_SUCCESS;

GlbError:
	if (NULL != m_pstTree->m_pstRoot) {
		GlbAcbmTreeClean(m_pstTree->m_pstRoot);
		GlbFree((void**)&m_pstTree->m_pstRoot);
	}

	return GLB_FAILURE;
}

int CGlbAcbm::GlbAcbmSetGSShift1(UCHAR* puszChar, int iDepth, int iShift)
{
	int iCount = 0;
	GLBACBMNODE_S* pstNode = m_pstTree->m_pstRoot;

	for (iCount = 0; iCount < iDepth; iCount ++) {
		if (NULL == (pstNode = pstNode->m_pstChild[puszChar[iCount]])) {
			goto GlbError;
		}
	}

	pstNode->m_iGSShift = pstNode->m_iGSShift < iShift ? pstNode->m_iGSShift : iShift;

	return GLB_SUCCESS;

GlbError:
	return GLB_FAILURE;
}

GLBACBMTREE_S* CGlbAcbm::GlbAcbmTreeInit(GLBACBMDATA_S* pstData, int iNumber)
{
	if (NULL == m_pstTree) {
		if (NULL != (m_pstTree = (GLBACBMTREE_S*)GlbMalloc(sizeof(GLBACBMTREE_S)))) {
			GlbAcbmTreeBuild(pstData, iNumber);
			GlbAcbmShift();
		}
	}

	return m_pstTree;
}

int CGlbAcbm::GlbAcbmSetGSShift2(UCHAR* puszOne, int iOne, UCHAR* puszTwo, int iTwo)
{
	int iCount1 = 0;
	int iCount2 = 0;
	int iIndex1 = 0;
	int iIndex2 = 0;
	int iOffset = 0;
	UCHAR ucFirst = '\0';

	ucFirst = puszOne[0];
	ucFirst = tolower(ucFirst);

	for (iCount1 = 1; iCount1 < iTwo; iCount1 ++) {
		if (ucFirst != tolower(puszTwo[iCount1])) {
			break;
		}
	}

	GlbAcbmSetGSShift1(puszOne, 1, iCount1);

	iCount1 = 1;
	while (true) {
		while ((iCount1 < iTwo) && (ucFirst != tolower(puszTwo[iCount1]))) iCount1 ++;
		if (iCount1 == iTwo) break;

		iIndex1 = 0;
		iIndex2 = iCount1;
		iOffset = iCount1;
		if (iOffset > m_pstTree->m_iMinPtnSize) break;

		while ((iIndex1 < iOne) && (iIndex2 < iTwo)) {
			if (tolower(puszOne[iIndex1 ++]) != tolower(puszTwo[iIndex2 ++])) {
				break;
			}
		}

		if (iIndex2 == iTwo) {
			for (iCount2 = iIndex1; iCount2 < iOne; iCount2 ++) {
				GlbAcbmSetGSShift1(puszOne, iCount2 + 1, iOffset);
			}
		}
		else {
			GlbAcbmSetGSShift1(puszOne, iIndex1 + 1, iOffset);
		}

		iCount1 ++;
	}

	return GLB_SUCCESS;
}

int CGlbAcbm::GlbAcbmSearch(UCHAR* puszText, int iText, GLBACBMMATCH_S stMatch[], int iMax)
{
	int iMatch = 0;
	register int iCur = 0;
	register int iBase = 0;
	register int iShift = 0;
	register int iGSShift = 0;
	register int iBCShift = 0;
	GLBACBMNODE_S* pstNode = NULL;

	if (iText < m_pstTree->m_iMinPtnSize) goto GlbReturn;

	iBase = iText - m_pstTree->m_iMinPtnSize;
	while (iBase >= 0) {
		iCur = iBase;
		pstNode = m_pstTree->m_pstRoot;

		while (NULL != pstNode->m_pstChild[puszText[iCur]]) {
			pstNode = pstNode->m_pstChild[puszText[iCur]];

			if (pstNode->m_iLabel >= 0) {
				stMatch[iMatch].m_iIndex = pstNode->m_iLabel;
				stMatch[iMatch].m_ulOffset = iBase;
				iMatch += 1;
				if (iMatch == iMax) goto GlbReturn;
			}

			if ((++ iCur) >= iText) break;
		}

		if (pstNode->m_iChild > 0){
			iGSShift = pstNode->m_pstChild[pstNode->m_ucChild]->m_iGSShift;
			if (iCur < iText) {
				iBCShift = m_pstTree->m_iBCShift[puszText[iCur]] + iBase - iCur;
			}
			else {
				iBCShift = 1;
			}
			iShift = iGSShift > iBCShift ? iBCShift : iGSShift;
			if (iShift <= 0 ) iShift = 1;
			iBase -= iShift;
		}
		else {
			iBase --;
		}
	}

GlbReturn:
	return iMatch;
}

void CGlbAcbm::GlbAcbmDisplayKey(GLBACBMDATA_S* pstData, int iNumber)
{
	int iCount = 0 ;

	for (iCount = 0; iCount < iNumber; iCount ++) {
		GLB_PRINT("%2d %s\n", iCount + 1, (char*)(pstData + iCount)->m_uszData);
	}

	return;
}

void CGlbAcbm::GlbAcbmDisplayMatch(GLBACBMDATA_S* pstData, GLBACBMMATCH_S stMatch[], int iMatch)
{
	int iCount = 0 ;

	for (iCount = 0; iCount < iMatch; iCount ++) {
		GLB_PRINT("Index: %d\n", stMatch[iCount].m_iIndex);
		GLB_PRINT("Offset: %lu\n", stMatch[iCount].m_ulOffset);
		GLB_PRINT("Keyword: %s\n\n", (char*)(pstData + stMatch[iCount].m_iIndex)->m_uszData);
	}

	return;
}

} /* GlbCls */
